#include<iostream>
#include <algorithm>  
using namespace std;

//BinaryTree基类
template <typename DT>
class BinaryTree
{
  private:
    class Node//Node基类
    {
      private:
        DT element;
        Node *left;
        Node *right;
      public:
        Node(DT _val)
          {element = _val; left = nullptr; right = nullptr;}
    
        virtual DT get_element() const//获取Node元素
        virtual void set_element(DT _val)//设置Node元素
    };
  Node *root;
  public:
    BinaryTree( ) : root{ nullptr }//初始化构造
    {}
    //The Big Five
    BinaryTree( const BinaryTree & rhs ) : root{ nullptr }
    {
        root = clone( rhs.root );
    }
    BinaryTree( BinaryTree && rhs ) : root{ rhs.root }
    {
        rhs.root = nullptr;
    }
    ~BinaryTree( )
    {
      makeEmpty( );
    }
    BinaryTree & operator=( const BinaryTree & rhs )
    {
        BinaryTree copy = rhs;
        std::swap( *this, copy );
        return *this;
    }
    BinaryTree & operator=( BinaryTree && rhs )
    {
        std::swap( root, rhs.root );       
        return *this;
    }

    virtual void insert(const DT & _val)=0//插入
    virtual void remove(const DT & _val)=0//删除
    const DT & FindMin(const DT & _val, Node * & t)const//搜索最小元素
    const DT & FindMax(const DT & _val, Node * & t)const//搜索最大元素
    bool contains(const DT &  _val)const //判断是否存在值为_val的节点
    bool isEmpty( ) const//判断BinaryTree是否为空
    void makeEmpty( )//清空BinaryTree
    void printTree( ) const//输出BinaryTree
      
  private:
    Node* FindMin(Node *t ) const
    Node* FindMax(Node *t ) const
    bool contains(const DT &  _val, Node * t)const
    void makeEmpty( Node * & t )
    void printTree( Node *t ) const

}

//BinaryTree的继承类BinarySearchTree
template <typename DT>
class BinarySearchTree : public BinaryTree<DT>
{
  private:
    class BSTNode : public Node<DT>{};//Node的继承类BSTNode 
    BSTNode* root;
  
    virtual void insert( const DT & _val, BSTNode * & t )
    virtual void remove( const DT & _val, BSTNode * & t ) 
};

//BinaryTree的继承类AVLTree
template <typename DT>
class AVLTree : public BinaryTree<DT> 
{
  private:
    class AVLNode : public Node<DT> //Node的继承类AVLNode
    {
      private:
        int height; //特有成员
    };
    AVLNode* root;
    static const int ALLOWED_IMBALANCE = 1;

    virtual void insert( const DT & _val, AVLNode * & t )
    {
      ...
      balance( t );
    }
    virtual void remove( const DT & _val, AVLNode * & t )
    {
      ...
      balance( t );
    }
    
    void balance( AVLNode * & t )
    int height( AVLNode *t ) const
  
    void rotateWithLeftChild( AVLNode * & k2 )
    void rotateWithRightChild( AVLNode * & k1 )
    void doubleWithLeftChild( AVLNode * & k3 )
    void doubleWithRightChild( AVLNode * & k1 )
};

//BinaryTree的继承类SplayTree
template <typename DT>
class SplayTree:public BinaryTree<DT>
{
  private:
    class SplayNode : public Node<DT>{};//Node的继承类SplayNode 
    SplayNode *root;
    SplayNode *nullNode;
  
    virtual void insert( const DT & _val, SplayNode * & t)
    virtual void remove(const DT & _val, SplayNode * & t)

    void reclaimMemory( SplayNode * t )
    void rotateWithLeftChild( SplayNode * & k2 )
    void rotateWithRightChild( SplayNode * & k1 )
};
